//给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。 
//
// 
//
// 示例 1： 
//
// 输入：c = 5
//输出：true
//解释：1 * 1 + 2 * 2 = 5
// 
//
// 示例 2： 
//
// 输入：c = 3
//输出：false
// 
//
// 示例 3： 
//
// 输入：c = 4
//输出：true
// 
//
// 示例 4： 
//
// 输入：c = 2
//输出：true
// 
//
// 示例 5： 
//
// 输入：c = 1
//输出：true 
//
// 
//
// 提示： 
//
// 
// 0 <= c <= 231 - 1 
// 
// Related Topics 数学 双指针 二分查找 
// 👍 321 👎 0

package com.cute.leetcode.editor.cn;
public class SumOfSquareNumbers {
    public static void main(String[] args) {
        new SumOfSquareNumbers().new Solution().judgeSquareSum(6);

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 判断一个非负整数是否为两个数的平方和
         * 1.还是用的双指针的方法，注意平方和可能越界，修改一下判断条件即可
         * 2.使用二分法进行遍历查找
         * 3.使用枚举的方法：时间复杂度 根号C
         *
         * 4.费马平方和：数学，不看了
         */
        public boolean judgeSquareSum(int c) {
            int min = 0;
            int max = (int) Math.pow(c, 0.5);
            while (min<=max){
                if (min*min<c-max*max) min++;
                else if (max*max-c>-min*min)max--;
                else return true;
            }
            return min*min==c;
        }

        /**
         * 使用二分法进行查找
         */
        public boolean judgeSquareSum1(int c) {
            int right = (int) Math.pow(c, 0.5);
            for (int i = 0; i <= right ; i++) {
                int res = binarySearch(i, right, c - i * i);
                if (res != -1) return true;
            }
            return false;
        }

        public int binarySearch(int left, int right , int target){
            while (left < right){
                int mid = left + (right - left)/2;
                if (mid*mid<target) left++;
                else right = mid;
            }
            if (left*left == target) return left;
            return -1;
        }

        public boolean enumSolution(int c){
            int max = (int) Math.sqrt(c);
            for (int a = 0; a <= max; a++) {
                int b = (int) Math.sqrt(c -a*a);
                if (a*a + b*b == c) return true;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}